package Algorithm.search.others;

/**
 * 162. 寻找峰值 https://leetcode.cn/problems/find-peak-element/
 * 题目简述：假设 nums[-1] = nums[n] = -∞，且任意两个相邻的数不等，返回数组中任意一个峰值。
 */
public class FindPeakElement {

    /**
     * 思路：由题设可知必定存在峰值，定义[low-1, low]局部递增，(high, high+2]局部递减，二分扫描维护区间定义，最后low的指向即为结果
     * 实际原理：当递增时，右边一定有峰值，右移low。当递减时，左边一定有峰值，左移high。
     */
    public int findPeakElement(int[] arr) {
        int n = arr.length;
        int low = 0, high = n - 2;
        while (low <= high) {
            int mid = low + high >> 1;
            if (arr[mid] < arr[mid+1]) //当递增时，右边一定有峰值
                low = mid + 1;
            else high = mid - 1; //当递减时，左边一定有峰值
        }
        return low;
    }
}
